Tags: #◇Computer Science #◇CCDSALG #◇Data Structures #◇Algorithms #◇Reviewer #◇Finals

CCDSALG Comprehensive Finals Reviewer

◇Overview

This reviewer synthesizes Data Structures and Algorithms (CCDSALG). It encompasses asymptotic complexity analysis ( $O, \Omega, \Theta$ ), linear data structures (arrays, singly/doubly linked lists, stacks, queues), nonlinear structures (trees, binary search trees, self-balancing AVL trees, binary min/max heaps), hash tables with collision resolution strategies, and graph theory algorithms (BFS, DFS, Dijkstra, Prim, Kruskal).

◇1. Master Asymptotic Complexity Matrix

Data Structure / Algorithm	Access / Search	Insertion	Deletion	Space Complexity
Array (Dynamic)	$O(1)$ / $O(n)$	$O(n)$ (amortized $O(1)$ at end)	$O(n)$	$O(n)$
Singly Linked List	$O(n)$	$O(1)$ (at head)	$O(1)$ (if node given, else $O(n)$ )	$O(n)$
Stack / Queue	$O(n)$	$O(1)$ (push / enqueue)	$O(1)$ (pop / dequeue)	$O(n)$
Hash Table	$O(1)$ avg / $O(n)$ worst	$O(1)$ avg / $O(n)$ worst	$O(1)$ avg / $O(n)$ worst	$O(n)$
Binary Search Tree	$O(h) \to O(n)$ worst	$O(h) \to O(n)$ worst	$O(h) \to O(n)$ worst	$O(n)$
AVL Tree	$O(\log n)$ guaranteed	$O(\log n)$ guaranteed	$O(\log n)$ guaranteed	$O(n)$
Binary Heap	$O(1)$ peek min/max	$O(\log n)$	$O(\log n)$ extract min/max	$O(n)$

Sorting Algorithms Comparison

Algorithm	Best Time	Average Time	Worst Time	Space	Stable?
Bubble / Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	No

◇2. AVL Tree Balance Factor & Rotations

The balance factor of a node $N$ is defined as:
$BF(N) = \text{height}(N.\text{left}) - \text{height}(N.\text{right}) \in \{-1, 0, 1\}$

LL Imbalance $\implies$ Single Right Rotation on $Z$ .
RR Imbalance $\implies$ Single Left Rotation on $Z$ .
LR Imbalance $\implies$ Double Rotation: Left Rotate on child $Y$ , then Right Rotate on $Z$ .
RL Imbalance $\implies$ Double Rotation: Right Rotate on child $Y$ , then Left Rotate on $Z$ .

◇3. Graph Algorithms Comparison

Breadth-First Search (BFS): Uses a Queue. Computes unweighted shortest paths in $O(V + E)$ .
Depth-First Search (DFS): Uses a Stack (or recursion). Detects cycles, topological sorting, and strongly connected components in $O(V + E)$ .
Dijkstra's Algorithm: Greedy algorithm using a Min-Priority Queue. Computes single-source shortest path for non-negative weights in $O((V + E) \log V)$ .
Kruskal's Algorithm: Greedy MST algorithm. Sorts edges and applies Disjoint Set Union (DSU / Union-Find) with union-by-rank and path compression in $O(E \log E)$ .
Prim's Algorithm: Greedy MST algorithm growing a single tree using a min-heap in $O(E \log V)$ .

◇4. High-Yield Exam Checklist

Does QuickSort worst-case occur on already-sorted arrays when picking the first/last element as pivot? YES ( $O(n^2)$ ).
In Open Addressing hashing, does quadratic probing eliminate primary clustering? YES, but it causes secondary clustering.
Is an AVL tree always a Binary Search Tree? YES (BST property + height-balanced property).
Can Dijkstra handle negative edge weights? NO (Must use Bellman-Ford).
How many edges are in a spanning tree of a connected graph with $V$ vertices? Exactly $V - 1$ edges.

Previous Topic: ◇CCPROG2, ◇CCDSTRU
Next Topic: ◇CSALGCM
Prerequisites: ◇Data Structures, Trees, Graphs, Sorting
Cross-Curricular Connections: ◇CSINTSY

[REV] CCDSALG COMPREHENSIVE FINALS REVIEWER